#include <cstdio>

#include "grafo.h"

Grafo::Grafo(int t){
    tam = t;
    nodos = new Nodo *[tam];
    
    for(int i = 0; i < tam; ++ i)
        nodos[i] = new Nodo(i + 1);

}

int Grafo::getTam(){
    return tam;
}

Nodo *Grafo::getNodo(int i){
    return nodos[i - 1];
}

void Grafo::agregarArco(int f, int d){
    nodos[f - 1]->agregarAdyacente(nodos[d - 1]);
    nodos[d - 1]->agregarAdyacente(nodos[f - 1]);
}

void Grafo::sortAdyacentes(){
    for(int i = 0; i < tam; ++ i){
        nodos[i]->sortAdyacentes();
    }
}

void Grafo::inicializar(){
    for(int i = 0; i < tam; ++ i){
        nodos[i]->inicializar();
    }
}

void Grafo::imprimir(){

    cout << setw(6) << "Numero" << setw(5) << " Color"  << " Nodos adyacentes" << endl;
    for(int i = 0; i < tam; ++ i){
        cout << setw(6) << nodos[i]->getId() << setw(5) << nodos[i]->getColor() << "  ";
        vector<Nodo*> ady = nodos[i]->getAdyacentes();
        for(vector<Nodo*>::iterator it = ady.begin(); it != ady.end(); ++ it){
            if (it != ady.begin()){
                cout << ",";
            }
            cout << (*it)->getId();
        }
        cout << endl;
    }
}
        
/*
 * Funcion a utilizar para comparar dos nodos
 */
bool cmp(Nodo *a, Nodo *b){
    return (a->grado >= b->grado);
}

int Grafo::auxiliarBrown(int n){
    int i, posRetorno, posMax = 0;
    vector<Nodo*>::iterator it;
    vector<Nodo*> ady;
    bool colorOk;
    
    /*
     *Se ha logrado una coloración nueva. Se guarda y se busca el siguiente 
     * paso del backtrack
     */
    if(n == tam){
        for(i = 0; i < tam; ++ i){
            if(nodos[i]->getColor() > nodos[posMax]->getColor()){
                posMax = i;
            }
            solParcial[i] = nodos[i]->getColor();
        }
        colorMax = nodos[posMax]->getColor();
        //cout << "Solucion encontrada con colorMax = " << colorMax << ", posMax = " << posMax << endl;
        //cout << "¿Tiene coloracion valida? " << (tieneColoracionValida() ? "Si" : "No") << endl;
        return posMax - 1;
    }
    
    //Se asignan las coloraciones posibles y se hacen las llamadas recursivas
    for(i = 0; i < colorMax; ++ i){
        colorOk = true;
        ady = nodos[n]->getAdyacentes();
        for(it = ady.begin(); it != ady.end(); ++ it){
            if((*it)->getColor() == i){
                colorOk = false;
                break;
            }
        }
        if(colorOk){
            nodos[n]->setColor(i);
            
            posRetorno = auxiliarBrown(n + 1);
            if(posRetorno != n){
                nodos[n]->setColor(-1);
                return posRetorno;
            }
        }
    }
    nodos[n]->setColor(-1);
    return n - 1;
}

void Grafo::colorearBrown(){
    int i;
    Nodo *dummy;

    //cout << "Ordenando el grafo" << endl;
    nodos = ordenarNodos(0, tam - 1);
    //cout << "Grafo ordenado" << endl;
    
    colorMax = tam;
    solParcial = new int[tam];
    
    nodos[0]->setColor(0);
    auxiliarBrown(1);
    
    for(i = 0; i < tam; ++ i)
        nodos[i]->setColor(solParcial[i]);
    
    delete[] solParcial;
}

void Grafo::colorearBrownKorman(){
    int i, d;
    Nodo *dummy;

    //cout << "Ordenando el grafo" << endl;
    nodos = ordenarNodos(0, tam - 1);
    //cout << "Grafo ordenado" << endl;
    
    colorMax = tam;
    solParcial = new int[tam];
    
    nodos[0]->setColor(0);
    reordenar(1);
    //cout << nodos[1]->getId() << endl;
    d = auxiliarBrownKorman(1);
    //cout << "Fuera del auxiliar" << endl;
    for(i = 0; i < tam; ++ i)
        nodos[i]->setColor(solParcial[nodos[i]->getId() - 1]);
    
    delete[] solParcial;
}

int Grafo::auxiliarBrownKorman(int n){
    int i, posRetorno, posMax = 0;
    vector<Nodo*> ady;
    bool colorOk;
    
    //cout << "Entrando con n = " << n << endl;
    /*
     *Se ha logrado una coloración nueva. Se guarda y se busca el siguiente 
     * paso del backtrack
     */
    if(n == tam){
        for(i = 0; i < tam; ++ i){
            if(nodos[i]->getColor() > nodos[posMax]->getColor()){
                posMax = i;
            }
            solParcial[nodos[i]->getId() - 1] = nodos[i]->getColor();
        }
        colorMax = nodos[posMax]->getColor();
        //cout << "Solucion encontrada con colorMax = " << colorMax << " posMax = " << posMax << endl;
        //cout << "¿Tiene coloracion valida? " << (tieneColoracionValida() ? "Si" : "No") << endl;
        return posMax - 1;
    }
    
    //Se asignan las coloraciones posibles y se hacen las llamadas recursivas
    for(i = 0; i < colorMax; ++ i){
        colorOk = true;
        //cout << "nodos[" << n << "] = " << nodos[n]->getId() << endl;
        ady = nodos[n]->getAdyacentes();
        //cout << "ady.end() - ady.begin() = " << (ady.end() - ady.begin()) << endl;
        vector<Nodo*>::iterator it;
        for(it = ady.begin(); it != ady.end(); ++ it){
            if(((*it)->getColor()) == i){
                colorOk = false;
                break;
            }
        }
        if(colorOk){
            nodos[n]->setColor(i);
            
            //cout << "Entrando a reordenar desde: " << n << endl;
            reordenar(n + 1);
            //cout << "Entrando a llamada recursiva desde " << n << endl;
            posRetorno = auxiliarBrownKorman(n + 1);
            //cout << "Ya afuera de la llamada desde " << n << " con posRetorno = " << posRetorno << endl;
            if(posRetorno != n){
                nodos[n]->setColor(-1);
                //cout << "Saliendo 0 desde n = " << n << endl;
                return posRetorno;
            }
        }
    }
    nodos[n]->setColor(-1);
    //cout << "Saliendo 1 desde n = " << n << endl;
    return n - 1;
}

void Grafo::reordenar(int n){
    
    //cout << "Reordenando desde posicion " << n << endl;
    int posMin, sumColor;
    int numColoresMin = colorMax + 1;
    int coloresAdy[colorMax];
    vector<Nodo *> ady;
    vector<Nodo *>::iterator it;
    Nodo *tmp;
    if(n == tam)
        return;
    
    for(int i = n; i < tam; ++i){
        memset(coloresAdy, 0, sizeof(int) * colorMax);
        ady = nodos[i]->getAdyacentes();
        
        //cout << "Para el nodo " << i << endl;
        for(it = ady.begin(); it != ady.end(); ++ it){
            //cout << "   Adyacente " << (*it)->getId() << " color " << (*it)->getColor() << endl;
            if((*it)->getColor() != -1){
                coloresAdy[(*it)->getColor()] = 1;
            }
        }
        
        sumColor = 0;
        for(int j = 0; j < colorMax; ++ j){
            sumColor += coloresAdy[j];
        }
        
        
        if(colorMax - sumColor < numColoresMin){
            posMin = i;
            numColoresMin = colorMax - sumColor;
        }
        //cout << "Para el nodo " << i << " se pueden asignar " << colorMax - sumColor << endl; 
    }
    //cout << "El valor de posMin es: " << posMin << endl;
    //cout << "El valor de numColoresMin es: " << numColoresMin << endl << endl;
    tmp = nodos[n];
    nodos[n] = nodos[posMin];
    nodos[posMin] = tmp;
}

bool Grafo::tieneColoracionValida(){
    int colorNodo, colorM = 0;
    vector<Nodo *>::iterator it;
    vector<Nodo *> ady;
    
    for(int i = 0; i < tam; ++i){
        colorNodo = nodos[i]->getColor();
        if(colorNodo > colorM)
            colorM = colorNodo;
        ady = nodos[i]->getAdyacentes();
        for(it = ady.begin(); it != ady.end(); ++ it)
            if(((*it)->getColor()) == colorNodo) {
                cout << (*it)->getId() << " es adyacente a " << i + 1 << endl;
                return false;
            }
    }
    colorMax = colorM;
    return true;
}

int Grafo::getColorMax(){
    return colorMax;
}

Nodo **Grafo::mezcla(Nodo **a, int tamA, Nodo **b, int tamB){
//     cout << "Entrando a mezcla con arreglos de tamano: " << tamA << " " << tamB << endl;
    int i = 0, j = 0, k = 0;
    Nodo **ret = new Nodo*[tamA + tamB];
    while((i != tamA) || (j != tamB)){
        if(i == tamA){
            ret[k] = b[j];
            ++ j;
        }else if(j == tamB){
            ret[k] = a[i];
            ++ i;
        }else{
            if(cmp(a[i], b[j])){
                ret[k] = a[i];
                ++ i;
            }else{
                ret[k] = b[j];
                ++ j;
            }
        }        
        ++ k;
    }
//     cout << "Arreglo ordenado a retornar: ";
//     for(int l = 0; l < tamA + tamB; ++ l){
//         cout << ret[l]->getId() << " ";
//     }
//     cout << endl;
//     delete []a;
//     delete []b;
    
    return ret;
}

Nodo **Grafo::ordenarNodos(int i, int f){
    Nodo **ret;
    
    //cout << "Analizando seccion: " << i << " - " << f << endl;
    //Si se tiene un solo elemento, retornar
    if(i == f){
        ret = new Nodo*[1];
        ret[0] = nodos[i];
//         cout << "Retornando el nodo: " << ret[0]->getId() << endl;
        return ret;
    }
    
//     cout << "Tamanos: " << (((i + f) / 2) - i + 1) << " " << (f - ((i + f) / 2 + 1) + 1) << endl;
    //Si no, hacer las llamadas recursivas y mezclar
    return mezcla(ordenarNodos(i, (i + f) / 2),
                  ((i + f) / 2) - i + 1,
                  ordenarNodos((i + f) / 2 + 1, f), 
                  f - ((i + f) / 2 + 1) + 1);
}

